package C048;

/**
 * ClassName: C04
 * Package: C048
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/15 13:59
 * @Version 1.0
 * @Since 1.0
 */
public class C04 {
    public static void main(String[] args) {
        int[][] arr = {{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0}};
        System.out.println(possibleToStamp(arr, 4,3));
    }


    public static boolean possibleToStamp(int[][] arr, int stampHeight, int stampWidth) {
        int[][] sum = new int[arr.length + 1][arr[0].length + 1];
        // 获取前缀和
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= arr[0].length; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i - 1][j - 1];
            }
        }

        /**
         1 1 3 4 3
         2 1 4 4 3
         3 1 5 4 3
         false
         */

        int[][] diff = new int[arr.length + 2][arr[0].length + 2];
        for (int i = 0, r1 = i + 1, r2 = i + stampHeight; i < arr.length && r1 <= arr.length && r2 <= arr.length; i++, r1++, r2++) {
            for (int j = 0, c1 = j + 1, c2 = j + stampWidth; j < arr[0].length && c1 <= arr[0].length && c2 <= arr[0].length; j++, c1++, c2++) {
//                System.out.println(r1 + " " + c1 + " " + r2 + " " + c2 + " " + getSum(sum, r1, c1, r2, c2));
                if (getSum(sum, r1, c1, r2, c2) == 0) {
                    // 设置
                    set(diff, r1, c1, r2, c2);
                }
            }
        }
        // 获取前缀和
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= arr[0].length; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            }
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 0 && diff[i + 1][j + 1] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void set(int[][] diff, int r1, int c1, int r2, int c2) {
        r2++;
        c2++;
        diff[r1][c1] += 1;
        diff[r2][c2] += 1;
        diff[r1][c2] -= 1;
        diff[r2][c1] -= 1;
    }

    private static int getSum(int[][] sum, int r1, int c1, int r2, int c2) {
        r1--;
        c1--;
        return sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
    }
}
